package euler.p001_050;

import euler.MainEuler;

public class Euler015 extends MainEuler {

    /*
        Starting in the top left corner of a 2×2 grid, there
        are 6 routes (without backtracking) to the bottom right corner.

        How many routes are there through a 20×20 grid?
     */
    public String resolve(int length) {

    	length++;

        long[][] minimalMatrix = new long[length][length];

        for (int i = length -1; i >= 0; i--) {
            minimalMatrix[i][length-1] = 1;
            minimalMatrix[length-1][i] = 1;
        }

        for (int i = length - 2; i >= 0; i--) {
        	minimalMatrix[i][i] = minimalMatrix[i+1][i] + minimalMatrix[i][i+1];
            for (int j = i-1; j >= 0; j--) {
                minimalMatrix[i][j] = minimalMatrix[i+1][j] + minimalMatrix[i][j+1];
                minimalMatrix[j][i] = minimalMatrix[j+1][i] + minimalMatrix[j][i+1];
            }
        }

        return String.valueOf(minimalMatrix[0][0]);
    }

}
